class Solution {
public:
    string reorganizeString(string s) {
        unordered_map<char,int> hash;
        for(auto e:s)
        {
            hash[e]++;
        }
        int n=s.size();
        vector<pair<char,int>> v(hash.begin(),hash.end());
        
        sort(v.begin(),v.end(),[&v](const pair<char,int>& a,const pair<char,int>& b){
            return a.second>b.second;
        });
        if(n%2==0)
        {
            if(v[0].second>n/2) return "";
        }
        else
        {
            if(v[0].second>n/2+1) return "";
        }
        string ret(n,'0');
        int i=0;
        for(auto& e:v)
        {
            while(e.second--)
            {
                if(i>=n) i=1;
                ret[i]=e.first;
                i+=2;
            }
        }
        return ret;


    }
};